package everydayGrade.t4;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-12-07-14:30
 * @Description: 1.0
 */
public class T1466 {
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] mp = creatTable(connections, n);
        return dfs(0, -1, mp);
    }

    public List<int[]>[] creatTable(int[][] edges, int n) {
        List<int[]>[] mp = new List[n];
        for (int i = 0; i < n; ++i) {
            mp[i] = new ArrayList<int[]>();
        }
        for (int[] e : edges) {
            int from = e[0], to = e[1];
            mp[from].add(new int[]{to, 1});
            mp[to].add(new int[]{from, 0});
        }
        return mp;
    }

    public int dfs(int p, int pre, List<int[]>[] mp) {
        int res = 0;
        for (int[] next : mp[p]) {
            if (next[0] != pre) {
                int to = next[0];
                res += next[1];
                res += dfs(to, p, mp);
            }
        }
        return res;
    }
}
